#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
using namespace std;
//class Solution {
//public:
//    int cnt, m, n;
//    bool check[7][7] = { false };
//    string word;
//    int dx[4] = { 0,0,-1,1 };
//    int dy[4] = { 1,-1,0,0 };
//    bool exist(vector<vector<char>>& _board, string _word)
//    {
//        board = _board;word = _word;
//        m = board.size();
//        n = board[0].size();
//        cnt = word.size();
//        for (int i = 0;i < board.size();i++)
//        {
//            for (int j = 0;i < board[0].size();j++)
//            {
//                if (board[i][j] == word[0])
//                {
//                    check[i][j] = true;
//                    if (dfs(i, j, 1))return true;
//                    check[i][j] = false;
//                }
//            }
//        }
//        return false;
//    }
//    bool dfs(int i, int j, int pos)
//    {
//        if (pos == cnt) return true;
//        int nx , ny ;
//        for (int k = 0;k < 4;k++)
//        {
//            nx = i + dx[k], ny = j + dx[k];
//            if (nx>=0 && nx<m && ny>=0 && ny<n && check[nx][ny] == false && board[nx][ny] == word[pos])
//            {
//                check[nx][ny] = true;
//                if (dfs(nx, ny, pos + 1)) return true;
//                check[nx][ny] = false;
//            }
//        }
//        return false;
////    }
//};
//class Solution6 {
//public:
//    bool check[6][6] = { false };
//    int m, n;
//    vector<vector<char>>& board;
//    string word;
//    int dx[4] = { 0,0,1,-1 };
//    int dy[4] = { 1,-1,0,0 };
//    bool exist(vector<vector<char>>& _board, string _word)
//    {
//        board = _board, word = _word, m = board.size(), n = board[0].size();
//        for (int i = 0;i < m;i++)
//            for (int j = 0;j < n;j++)
//            {
//                if (board[i][j] == word[0])
//                {
//                    check[i][j] = true;
//                    if (dfs(i, j, 1)) return true;
//                    check[i][j] = false;
//                }
//            }
//        return false;
//    }
//    bool dfs(int i, int j, int pos)
//    {
//        if (pos == word.size()) return true;
//        for (int k = 0;k < 4;k++)
//        {
//            int x = i + dx[k], y = j + dy[k];
//            if (x >= 0 && x < m && y >= 0 && y < n && check[x][y] == false && board[x][y] == word[pos])
//            {
//                check[x][y] = true;
//                if (dfs(x, y, pos + 1)) return true;
//                check[x][y] = false;
//            }
//        }
//        return false;
//
//    }
//};
//class Solution9
//{
//public:
//    bool check[16][16];
//    int Max = 0, m, n;
//    int dx[4] = { 0,0,1,-1 };
//    int dy[4] = { 1,-1,0,0 };
//    int getMaximumGold(vector<vector<int>>& grid)
//    {
//        m = grid.size(), n = grid[0].size();
//        for (int i = 0;i < m;i++)
//        {
//            for (int j = 0;j < n;j++)
//            {
//                if (grid[i][j] != 0)
//                {
//                    check[i][j] = true;
//                    dfs(grid, i, j, 0);
//                    check[i][j] = false;
//                }
//            }
//        }
//        return Max;
//    }
//    void dfs(vector<vector<int>>& grid, int x, int y, int cur)
//    {
//        cur += grid[x][y];
//        for (int i = 0;i < 4;i++)
//        {
//            int nx = x + dx[i], ny = y + dy[i];
//            if (ny >= 0 && ny < n && nx < m && nx >= 0 && check[x + dx[i]][y + dy[i]] == false && grid[nx][ny] != 0)
//            {
//                check[x + dx[i]][y + dy[i]] = true;
//                dfs(grid, x + dx[i], y + dy[i], cur);
//                check[x + dx[i]][y + dy[i]] = false;
//            }
//        }
//        Max = max(cur, Max);
//        return;
//
//    }
//};
class Solution
{
public:
    bool memo[200][200] = { 0 };
    int longestIncreasingPath(vector<vector<int>> matrix)
    {
        int ret = 0;
        for (int i = 0;i < matrix.size();i++)
            for (int j = 0;j < matrix[0].size();j++)
                ret = max(ret, dfs(matrix, i, j));
        return ret;
    }
    int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };
    int dfs(vector<vector<int>>& matrix, int i, int j)
    {
        if (memo[i][j] != 0) return memo[i][j];
        int ret = 0;
        for (int k = 0;k < 4;k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < matrix.size() && y >= 0 && y<matrix[0].size() && matrix[x][y]>matrix[i][j])
                ret = max(ret, dfs(matrix, x, y));
        }
        memo[i][j] = ret + 1;
        return memo[i][j];
    }
};
using namespace std;
int main()
{
    vector<vector<int>> vv = {
        {3,4,5},
        {3,2,6},
        {2,2,1}
    };
    Solution().longestIncreasingPath(vv);
	return 0;
}